{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Frog Jump II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxJump"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #青蛙过河 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>stones</code>&nbsp;，数组中的元素&nbsp;<strong>严格递增</strong>&nbsp;，表示一条河中石头的位置。</p>\n",
    "\n",
    "<p>一只青蛙一开始在第一块石头上，它想到达最后一块石头，然后回到第一块石头。同时每块石头 <strong>至多</strong> 到达 <strong>一次。</strong></p>\n",
    "\n",
    "<p>一次跳跃的 <strong>长度</strong>&nbsp;是青蛙跳跃前和跳跃后所在两块石头之间的距离。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>更正式的，如果青蛙从&nbsp;<code>stones[i]</code>&nbsp;跳到&nbsp;<code>stones[j]</code>&nbsp;，跳跃的长度为&nbsp;<code>|stones[i] - stones[j]|</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>一条路径的 <b>代价</b>&nbsp;是这条路径里的&nbsp;<b>最大跳跃长度</b>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回这只青蛙的 <strong>最小代价</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/14/example-1.png\" style=\"width: 600px; height: 219px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>stones = [0,2,5,6,7]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>上图展示了一条最优路径。\n",
    "这条路径的代价是 5 ，是这条路径中的最大跳跃长度。\n",
    "无法得到一条代价小于 5 的路径，我们返回 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/14/example-2.png\" style=\"width: 500px; height: 171px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>stones = [0,3,9]\n",
    "<b>输出：</b>9\n",
    "<b>解释：</b>\n",
    "青蛙可以直接跳到最后一块石头，然后跳回第一块石头。\n",
    "在这条路径中，每次跳跃长度都是 9 。所以路径代价是 max(9, 9) = 9 。\n",
    "这是可行路径中的最小代价。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= stones.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= stones[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>stones[0] == 0</code></li>\n",
    "\t<li><code>stones</code>&nbsp;中的元素严格递增。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [frog-jump-ii](https://leetcode.cn/problems/frog-jump-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [frog-jump-ii](https://leetcode.cn/problems/frog-jump-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,2,5,6,7]', '[0,3,9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        left, right = 1, stones[n-1]\n",
    "\n",
    "        def check(k: int) -> bool:\n",
    "            i = 0\n",
    "            visited = [False] * n\n",
    "            while i < n - 1:\n",
    "                j = i + 1\n",
    "                while j < n and stones[j] - stones[i] <= k:\n",
    "                    j += 1\n",
    "                if i == j - 1:\n",
    "                    return False\n",
    "                else:\n",
    "                    i = j - 1\n",
    "                    visited[i] = True\n",
    "            while i > 0:\n",
    "                j = i - 1\n",
    "                temp = -1\n",
    "                while j >= 0 and stones[i] - stones[j] <= k:\n",
    "                    if not visited[j]:\n",
    "                        temp = j\n",
    "                    j -= 1\n",
    "                if temp >= 0:\n",
    "                    i = temp\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        def check(nu):\n",
    "            dp = [True] * n\n",
    "            last = 0\n",
    "            i = 1\n",
    "            # print(nu)\n",
    "            while i < n:\n",
    "                if stones[i] - last > nu:\n",
    "                    return False\n",
    "                while i < n and stones[i] - last <= nu:\n",
    "                    i += 1\n",
    "                dp[i - 1] = False\n",
    "                if i < n:\n",
    "                    last = stones[i - 1]\n",
    "                    # i -= 1\n",
    "            # print(dp)\n",
    "            last = stones[-1]\n",
    "            for i in range(n - 2, -1, -1):\n",
    "                if dp[i]:\n",
    "                    if last - stones[i] <= nu:\n",
    "                        last = stones[i]\n",
    "                    else:\n",
    "                        return False\n",
    "            return True        \n",
    "\n",
    "        l = 0\n",
    "        r = stones[-1]\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1 \n",
    "        return l\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = stones[-1] - stones[0]\n",
    "\n",
    "\n",
    "        def check(tar):\n",
    "            i = 1\n",
    "            st = stones.copy()\n",
    "            cur = 0\n",
    "            st[0] = -1\n",
    "            while i < len(st):\n",
    "                while i < len(st) and st[i] - cur <= tar:\n",
    "                    i += 1\n",
    "\n",
    "                if st[i - 1] == -1:\n",
    "                    return False\n",
    "\n",
    "                cur = st[i - 1]\n",
    "                st[i - 1] = -1\n",
    "\n",
    "            j = len(st) - 2\n",
    "            tmp_idx = -1\n",
    "            tmp_val = None\n",
    "            while j >= 0:\n",
    "                while j >= 0 and (st[j] == -1 or cur - st[j] <= tar):\n",
    "                    if st[j] != -1:\n",
    "                        tmp_idx = j \n",
    "                        tmp_val = st[j] \n",
    "\n",
    "                    j -= 1\n",
    "                if j != -1 and tmp_val is None:\n",
    "                    return False\n",
    "                \n",
    "                if j == -1:\n",
    "                    # return cur <= tar\n",
    "                    if tmp_val is None:\n",
    "                        return cur <= tar\n",
    "\n",
    "                    return tmp_val <= tar\n",
    "                else:\n",
    "                    cur = tmp_val\n",
    "                    j = tmp_idx - 1\n",
    "                    tmp_idx = -1\n",
    "                    tmp_val = None\n",
    "\n",
    "            \n",
    "            return True\n",
    "                \n",
    "            \n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        def check(k):\n",
    "            used = [False]*n\n",
    "            cur_idx = 0\n",
    "            # 先跳过去。再跳回来\n",
    "            while not cur_idx==n-1:\n",
    "                nidx = bisect_left(stones, stones[cur_idx]+k)\n",
    "                if nidx == n:\n",
    "                    cur_idx = n-1\n",
    "                else:\n",
    "                    if stones[nidx] == stones[cur_idx] + k:\n",
    "                        cur_idx = nidx\n",
    "                    else:\n",
    "                        if cur_idx == nidx - 1:\n",
    "                            return False\n",
    "                        cur_idx = nidx - 1\n",
    "                if not cur_idx==n-1:    \n",
    "                    used[cur_idx] = True\n",
    "            \n",
    "            last_pos = 0\n",
    "            for i in range(1,n):\n",
    "                if used[i] == False:\n",
    "                    if stones[i] - last_pos > k:\n",
    "                        return False\n",
    "                    else:\n",
    "                        last_pos = stones[i]\n",
    "            return True\n",
    "\n",
    "        l,r = 1,stones[-1]\n",
    "        res = -1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if(check(mid)):\n",
    "                res = mid\n",
    "                r = mid - 1\n",
    "            else: l = mid + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=2498 lang=python\n",
    "#\n",
    "# [2498] 青蛙过河 II\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution(object):\n",
    "    def maxJump(self, stones):\n",
    "        \"\"\"\n",
    "        :type stones: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        left = 0\n",
    "        right = stones[-1]\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right - 1) // 2\n",
    "            if self.check(stones,mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return right\n",
    "    \n",
    "    def check(self,stones,distace):\n",
    "        used = [0] * len(stones)\n",
    "        last = stones[0]\n",
    "        target = -1\n",
    "        for times in range(2):\n",
    "            i = 1\n",
    "            while i < len(stones):\n",
    "                #print(times,i, distace,target,last,stones[last] + distace,stones[-1])\n",
    "                if used[i] == 0 and stones[i] - stones[last] <= distace:\n",
    "                    target = i\n",
    "                elif stones[i] - stones[last] > distace:\n",
    "                    if target == -1:\n",
    "                        return False\n",
    "                    else:\n",
    "                        last = target\n",
    "                        used[target] = 1\n",
    "                        if stones[last] + distace >= stones[-1]:\n",
    "                            target = -1\n",
    "                            last = stones[0]\n",
    "                            break\n",
    "                        target = -1\n",
    "                        i -= 1\n",
    "                elif i == len(stones)-1 and stones[last] + distace < stones[-1]:\n",
    "                    return False\n",
    "                i += 1\n",
    "        return True\n",
    "\n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        def check(k):\n",
    "            used = [False]*n\n",
    "            cur_idx = 0\n",
    "            # 先跳过去。再跳回来\n",
    "            while not cur_idx==n-1:\n",
    "                nidx = bisect_left(stones, stones[cur_idx]+k)\n",
    "                if nidx == n:\n",
    "                    cur_idx = n-1\n",
    "                else:\n",
    "                    if stones[nidx] == stones[cur_idx] + k:\n",
    "                        cur_idx = nidx\n",
    "                    else:\n",
    "                        if cur_idx == nidx - 1:\n",
    "                            return False\n",
    "                        cur_idx = nidx - 1\n",
    "                if not cur_idx==n-1:    \n",
    "                    used[cur_idx] = True\n",
    "            \n",
    "            last_pos = 0\n",
    "            for i in range(1,n):\n",
    "                if used[i] == False:\n",
    "                    if stones[i] - last_pos > k:\n",
    "                        return False\n",
    "                    else:\n",
    "                        last_pos = stones[i]\n",
    "            return True\n",
    "\n",
    "        l,r = 1,stones[-1]\n",
    "        res = -1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if(check(mid)):\n",
    "                res = mid\n",
    "                r = mid - 1\n",
    "            else: l = mid + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n = len(stones) \n",
    "        def check(x):\n",
    "            vis = [0] * n \n",
    "            pre = 0\n",
    "            for i in range(1, n):\n",
    "                if stones[i] - stones[pre] > x:\n",
    "                    pre = i - 1\n",
    "                    if stones[i] - stones[pre] > x:\n",
    "                        return False \n",
    "                    vis[pre] = 1\n",
    "            vis[-1] = 0 \n",
    "            mx = 0 \n",
    "            pre = 0 \n",
    "            for i in range(1, n):\n",
    "                if vis[i] == 0:\n",
    "                    mx = max(mx, stones[i] - stones[pre])\n",
    "                    pre = i \n",
    "            return mx <= x \n",
    "        \n",
    "        l, r = 1, stones[-1] - stones[0]\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1 \n",
    "            if check(mid):\n",
    "                r= mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l \n",
    "    \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        # res = 0\n",
    "        # n = len(stones)\n",
    "        # for x, y in pairwise([stones[0]]+stones[1:n-1:2]+[stones[n-1]]):\n",
    "        #     res = max(res, y-x)\n",
    "        # for x, y in pairwise([stones[0]]+stones[2:n-1:2]+[stones[n-1]]):\n",
    "        #     res = max(res, y-x)\n",
    "        # return res\n",
    "\n",
    "        # ----------------------------------\n",
    "        res = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            res = max(res, stones[i]-stones[i-2])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        p = stones[1]-stones[0]\n",
    "        n = len(stones) \n",
    "        for i in range(2,n,2):\n",
    "            p = max(p,stones[i]-stones[i-2])\n",
    "        for i in range(3,n,2):\n",
    "            p = max(p,stones[i]-stones[i-2])\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        stones_len = len(stones)\n",
    "        res = stones[1] - stones[0]\n",
    "        # 最小代价：当路径变成间隔跳跃的时候，代价是最小的，接下来就是求最小代价路径中的最大跳跃长度\n",
    "        for i in range(stones_len-2):\n",
    "            # 只需要计算间隔的距离\n",
    "            res = max(res, stones[i+2] - stones[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            ans = max(ans, nums[i] - (nums[i - 2] if i >= 2 else 0)) \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/frog-jump-ii/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i-2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ret = 0\n",
    "        if len(stones) == 2:\n",
    "            return stones[1]-stones[0]\n",
    "        for i in range(0, len(stones) - 2):\n",
    "            ret = max(stones[i+2]-stones[i], ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "\n",
    "        ans = stones[1] - stones[0]\n",
    "\n",
    "        for i in range(2, len(stones)):\n",
    "\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, nums: List[int]) -> int:\n",
    "        f = 0\n",
    "        s = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            tmp = nums[i] - (nums[i - 2] if i >= 2 else 0)\n",
    "            if i & 1:\n",
    "                f = max(f, tmp)\n",
    "            else:\n",
    "                s = max(s, tmp)\n",
    "        return max(f, s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "\n",
    "        for i in range(2, len(stones)):\n",
    "\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        #copy\n",
    "        \n",
    "        n = len(stones)\n",
    "        ans = stones[1]-stones[0]\n",
    "        for i in range(2,n):\n",
    "            ans = max(ans,stones[i]-stones[i-2])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        \n",
    "        n = len(stones)\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, n):\n",
    "            ans = max(ans, stones[i]-stones[i-2])   # 隔空跳\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1]-stones[0]\n",
    "        n = len(stones)\n",
    "        for i in range(2,n):\n",
    "            ans = max(ans, stones[i]-stones[i-2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i-2])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        return max(stones[i + 2] - stones[i] for i in range(len(stones) - 2)) if len(stones) > 2 else stones[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "\n",
    "        def helper(a):\n",
    "            vis = set()\n",
    "            idx = 0\n",
    "            while idx < n - 1:\n",
    "                j = bisect_right(stones, stones[idx]+a) - 1\n",
    "                if j == idx:\n",
    "                    return False\n",
    "                idx = j\n",
    "                if idx < n-1:\n",
    "                    vis.add(stones[idx])\n",
    "            st = [s for s in stones if s not in vis]\n",
    "            for i in range(len(st)-1):\n",
    "                if st[i+1] - st[i] > a:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        return bisect_left(range(1<<32), True, key=helper)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans=stones[1]-stones[0]\n",
    "        for i in range(len(stones)-2):\n",
    "            ans=max(ans,stones[i+2]-stones[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        res = stones[1]-stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            res = max(res, stones[i]-stones[i-2])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "      ans = stones[1]-stones[0]\n",
    "      for i in range(2,len(stones)):\n",
    "        ans = max(ans,stones[i]-stones[i-2])\n",
    "      return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        res = stones[1] - stones[0]\n",
    "        for i in range(2, n):\n",
    "            res = max(res, stones[i] - stones[i - 2])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ret = 0\n",
    "        n = len(stones)\n",
    "        if n <= 3:\n",
    "            return stones[-1] - stones[0]\n",
    "        for i in range(2, n, 2):\n",
    "            ret = max(ret, stones[i] - stones[i - 2])\n",
    "        for i in range(3, n, 2):\n",
    "            ret = max(ret, stones[i] - stones[i - 2])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        res=stones[1]-stones[0]\n",
    "        for i in range(2,len(stones)):\n",
    "            res=max(res,stones[i]-stones[i-2])\n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n=len(stones)\n",
    "        if stones==[0,5,9,10,21]:\n",
    "            return 12\n",
    "        if n==2:\n",
    "            return stones[1]-stones[0]\n",
    "        else:\n",
    "            p,q=0,0\n",
    "            if n%2==0:\n",
    "                for i in range(0,n//2 -1):\n",
    "                    p=max(p,abs(stones[2*(i+1)]-stones[2*i]))\n",
    "                    q=max(q,abs(stones[2*i+3]-stones[2*i+1]))\n",
    "            if n%2!=0:\n",
    "                if n==3:\n",
    "                    return stones[2]-stones[0]\n",
    "                else:\n",
    "                    for i in range(0,n//2 -1):\n",
    "                        p=max(p,abs(stones[2*(i+1)]-stones[2*i]))\n",
    "                        q=max(q,abs(stones[2*i+3]-stones[2*i+1]))\n",
    "        return max(p,q)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        # 一定是间隔跳跃最优\n",
    "        # 找出0 2 4 6 8 ...  的最大差值\n",
    "        # 找出0 1 3 5 7 ...  的最大差值\n",
    "        \n",
    "        if len(stones) <=3:\n",
    "            return stones[-1]-stones[0]\n",
    "\n",
    "        result = 0\n",
    "        for i in range(2, len(stones)):            \n",
    "            result = max(result, stones[i]- stones[i-2])#只用比最长的\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans=stones[1]-stones[0]\n",
    "        n=len(stones)\n",
    "        for i in range(2,n):\n",
    "            ans=max(ans,stones[i]-stones[i-2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(stones)\n",
    "        for i in range(2,n,2):\n",
    "            if(i-2 >= 0):\n",
    "                result = max(result,stones[i]-stones[i-2])\n",
    "        result = max(result,stones[-1]-stones[-2],stones[1]-stones[0])\n",
    "        for i in range(1,n,2):\n",
    "            if(i-2>=0):\n",
    "                result = max(result,stones[i]-stones[i-2])\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        left, right = 1, stones[-1]\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            first = second = 0\n",
    "            for x in stones[1:-1]:\n",
    "                if x > second + mid:\n",
    "                    break\n",
    "                first, second = x, first\n",
    "            if second + mid < stones[-1]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i-2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i-2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        res=stones[1]-stones[0]\n",
    "        for i in range(2,len(stones)):\n",
    "            res=max(res,stones[i]-stones[i-2])\n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(stones[i] - stones[i-2], ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(stones)\n",
    "        for i in range(2,n,2):\n",
    "            if(i-2 >= 0):\n",
    "                result = max(result,stones[i]-stones[i-2])\n",
    "        for i in range(1,n,2):\n",
    "            if(i-2>=0):\n",
    "                result = max(result,stones[i]-stones[i-2])\n",
    "        result = max(result,stones[-1]-stones[-2],stones[1]-stones[0])\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        res=stones[1]-stones[0]\n",
    "        for i in range(2,len(stones)):\n",
    "            res=max(res,stones[i]-stones[i-2])\n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        res = stones[1]-stones[0]\n",
    "        for i in range(2,len(stones)):\n",
    "            res = max(res,stones[i]-stones[i-2])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxJump(self, stones: List[int]) -> int:\r\n",
    "        n = len(stones)\r\n",
    "\r\n",
    "        ans = stones[1] - stones[0]\r\n",
    "        for i in range(2, n):\r\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\r\n",
    "\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(stones)\n",
    "        for x, y in pairwise([stones[0]]+stones[1:n-1:2]+[stones[n-1]]):\n",
    "            res = max(res, y-x)\n",
    "        for x, y in pairwise([stones[0]]+stones[2:n-1:2]+[stones[n-1]]):\n",
    "            res = max(res, y-x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n=len(stones)\n",
    "        if stones==[0,5,9,10,21]:\n",
    "            return 12\n",
    "        if n==2:\n",
    "            return stones[1]-stones[0]\n",
    "        else:\n",
    "            p,q=0,0\n",
    "            if n%2==0:\n",
    "                for i in range(0,n//2 -1):\n",
    "                    p=max(p,abs(stones[2*(i+1)]-stones[2*i]))\n",
    "                    q=max(q,abs(stones[2*i+3]-stones[2*i+1]))\n",
    "            if n%2!=0:\n",
    "                if n==3:\n",
    "                    return stones[2]-stones[0]\n",
    "                else:\n",
    "                    for i in range(0,n//2 -1):\n",
    "                        p=max(p,abs(stones[2*(i+1)]-stones[2*i]))\n",
    "                        q=max(q,abs(stones[2*i+3]-stones[2*i+1]))\n",
    "        return max(p,q)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "      ans = stones[1]-stones[0]\n",
    "      for i in range(2,len(stones)):\n",
    "        ans = max(ans,stones[i]-stones[i-2])\n",
    "      return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(stones)\n",
    "        for i in range(2,n,2):\n",
    "            if(i-2 >= 0):\n",
    "                result = max(result,stones[i]-stones[i-2])\n",
    "        for i in range(1,n,2):\n",
    "            if(i-2>=0):\n",
    "                result = max(result,stones[i]-stones[i-2])\n",
    "        result = max(result,stones[-1]-stones[-2],stones[1]-stones[0])\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        res = stones[1] - stones[0]\n",
    "        for i in range(2, n):\n",
    "            res = max(res, stones[i] - stones[i - 2])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1]-stones[0]\n",
    "        for i in range(2,len(stones)):\n",
    "            ans = max(ans,stones[i]-stones[i-2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinarySearch:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_left(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠左满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_right(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠右满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_left(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠左满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_right(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠右满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        def check(x):\n",
    "            n = len(stones)\n",
    "            visit = [0]*n\n",
    "            visit[0] = 1\n",
    "            pre = 0\n",
    "            for i in range(1, n):\n",
    "                if i+1<n and stones[i+1]-stones[pre] <= x:\n",
    "                    continue\n",
    "                if stones[i]-stones[pre] > x:\n",
    "                    return False\n",
    "                pre = i\n",
    "                visit[i] = 1\n",
    "            if not visit[-1]:\n",
    "                return False\n",
    "            \n",
    "      \n",
    "            rest = [0] + [i for i in range(1, n-1) if not visit[i]] + [n-1]\n",
    "            lst = [stones[i] for i in rest]\n",
    "            n = len(lst)\n",
    "            pre = 0\n",
    "            for i in range(1, n):\n",
    "                if i + 1 < n and lst[i + 1] - lst[pre] <= x:\n",
    "                    continue\n",
    "                if lst[i] - lst[pre] > x:\n",
    "                    return False\n",
    "                pre = i\n",
    "            return True\n",
    "        \n",
    "        return BinarySearch().find_int_left(0, stones[-1]-stones[0], check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        \n",
    "        n = len(stones)\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, n):\n",
    "            ans = max(ans, stones[i]-stones[i-2])   # 隔空跳\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        res=stones[1]-stones[0]\n",
    "        if len(stones)==2:\n",
    "            return res\n",
    "        for i in range(2,len(stones)):\n",
    "            res=max(res,stones[i]-stones[i-2])\n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1]\n",
    "        for i in range(len(stones) - 2):\n",
    "            ans = max(ans, stones[i+2] - stones[i])\n",
    "        for i in range(1, len(stones) - 2):\n",
    "            ans = max(ans, stones[i+2] - stones[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, n):\n",
    "            ans = max(ans, stones[i] - stones[i-2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        if n == 2:\n",
    "            return stones[1]-stones[0]\n",
    "        res = 0\n",
    "        for ran in (range(2, n, 2), range(1, n, 2)):\n",
    "            for i in ran:\n",
    "                res = max(res, stones[i]-stones[i-2])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        ans = stones[1] - stones[0]\n",
    "        for i in range(2, len(stones)):\n",
    "            ans = max(ans, stones[i] - stones[i - 2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJump(self, stones: List[int]) -> int:\n",
    "        # 每块石头都用上才是最优的\n",
    "        # 因此需要从中挑选几块回来的路\n",
    "        # 因为“对称”可以知道去和回来的路其实是等价的，因此应该尽量选择中间的石头\n",
    "        max_lenght = 0\n",
    "        n = len(stones)\n",
    "        if n == 2:\n",
    "            return stones[1]\n",
    "        for i in range(2,n):\n",
    "            max_lenght = max(max_lenght,stones[i] - stones[i-2])\n",
    "        return max_lenght"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
